package Algorithm;

import Structure.Graph;
import Structure.GraphGenerator;
import Structure.Node;

import java.util.*;

/**
 * @Author: ylc
 * @Description:拓扑排序
 * @Date Created in 2022-06-06 18:57
 */
public class TopologySort {
    /**
     * 拓扑排序
     * @param graph 有向无环图，且有入度为0的点
     * @return
     */
    public static List<Node> topologySort(Graph graph){
        // key:节点   value:入度数
        Map<Node,Integer> inMap = new HashMap<>();
        Queue<Node> zeroInqueue = new LinkedList<>();
        for (Node curNode :
                graph.nodes.values()) {
            inMap.put(curNode,curNode.in);
            if(curNode.in == 0){
                zeroInqueue.offer(curNode);
            }
        }
        List<Node> result = new ArrayList<>();
        while(!zeroInqueue.isEmpty()){
            Node curNode = zeroInqueue.poll();
            result.add(curNode);
            for (Node next :
                    curNode.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if(inMap.get(next) == 0){
                    zeroInqueue.offer(next);
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        Graph graph = create();
        List<Node> nodes = topologySort(graph);
        for (Node node :
                nodes) {
            System.out.print(node.value + "->");
        }
    }
    public static Graph create(){
        int[][] arr = {
                {0,1,2},{0,2,3},{0,3,4},
                {0,1,3},{0,2,4}
        };

        return GraphGenerator.generateGraph(arr);
    }

}
